public class MinCostClimbingStairs {
    // 最小花费爬楼梯
    // https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        int[] dp = new int[cost.length+1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

    /**
     * 空间优化
     * @param cost
     * @return
     */
    public int minCostClimbingStairs2 (int[] cost) {
        // write code here
        int num1 = 0;
        int num2 = 0;
        for (int i = 2; i <= cost.length; i++) {
            int tmp = Math.min(num1 + cost[i-2], num2 + cost[i-1]);
            num1 = num2;
            num2 = tmp;
        }
        return num2;
    }
}
